import java.util.Stack;

/**
 * 有效的括号
 * https://leetcode-cn.com/problems/valid-parentheses/
 * @author yinye
 * @since 2020-02-01 17:24
 */
public class ValidParentheses {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char parentheses = s.charAt(i);
            // 左括号进行入栈
            if (parentheses == '(' || parentheses == '{' || parentheses == '[') {
                stack.push(parentheses);
                continue;
            }

            if (stack.isEmpty()) {
                return false;
            }

            //右括号开始进行匹配
            Object leftParentheses = stack.pop();
            if((parentheses == ')' && !leftParentheses.equals('('))
                    || (parentheses == '}' && !leftParentheses.equals('{'))
                    || (parentheses == ']' && !leftParentheses.equals('['))){
                return false;
            }
        }

        //左括号全部匹配完毕，即栈为空时为才为合法
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String [] array = new String[]{"()" , "()[]{}" , "(]" , "([)]" , "{[]}"};
        for (int i = 0; i < array.length; i++) {
            System.out.println( array[i] + " = " + new ValidParentheses().isValid(array[i]));
        }
    }
}
